Voćnjak
време | меморија | улаз | излаз |
---|---|---|---|
1 s | 128 Mb | стандардни излаз | стандардни улаз |
Petar ima ogroman voćnjak šljiva koji je idealno organizovao tako da su šljive poređane u redova (vrsta) i kolona. Visine svih stabala su pozitivni celi brojevi. Ne postoje dva stabla iste visine. Pri tome je stabla tako oblikovao tako da za svaku vrstu važi da visine stabala sleva nadesno obrazuju rastući ili opadajući niz (mogu postojati vrste poređane u rastućem, ali isto tako i vrste poređane u opadajućem poretku, na potpuno slučajan način poređane). Slično za svaku kolonu važi da visine stabala od prvog prema poslednjem obrazuju rastući ili opadajući niz (mogu postojati kolone u kojima su poređane u rastućem poretku i kolone u kojima su poređane u opadajućem poretku, ali poredak vama nije poznat). Vrste su numerisane brojevima od do , a kolone brojevima od do . Na raspolaganju imate funkciju (kasnije će biti detaljno opisana) kojom možete dobiti visinu stabla koje se nalazi u određenoj vrsti i koloni (zvaćemo tu funkciju upit). Potrebno je da sa što manje upita odredite da li u voćnjaku postoji stablo zadate visine i poziciju tog stabla, ako postoji (redni broj vrste i redni broj kolone). Zato će biti zadat prirodan broj . Ako vaš program u ne više od upita odgovori tačno smatra se da je vaš program korektno rešio taj test primer, u suprotnom, smatra se da je rešenje primera netačno.
Opisi funkcija
Potrebno je da implementirate funkciju
koja treba da odredi da li se u voćnjaku sa vrsta i kolona nalazi stablo visine i ako se nalazi odredi redni broj vrste i redni broj kolone u kome se nalazi stablo visine . Ako stablo ne postoji, onda vrednosti za redni broj vrste i redni broj kolone treba da budu 0. je predviđeni broj upita.
Na raspolaganju imate funkciju
koja treba da vrati visinu stabla koje se nalazi u vrsti i kooni . Ako koordinate i nisu u dozvoljenim granicama, funkcija vraća vrednost .
Primer
Neka je , a matrica sa visinama stabala:
3 6 10 15 5 9 13 18 31 27 23 20 45 28 32 25
Ako je prvi upit bio za polje odgovor bi bio . Ako je drugi upit za polje odgovor bi bio . Konačno, ako je treći upit za polje odgovor bi bio 9, pa bi vaša funkcija mogla da vrati rešenje , .
Ograničenja
- Visine stabala si između i
Podzadaci
- Podzadatak 1 [8 poena]: , .
- Podzadatak 2 [14 poena]: , .
- Podzadatak 3 [24 poena]: , .
- Podzadatak 4 [54 poena]: , .
Detalji implementacije
Potrebno je da pošaljete tačno jedan fajl vocnjak.cpp
ili vocnjak.pas
, koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.
U zavisnosti od programskog jezika koji koristite, vaša funkcija/procedura mora biti sledećeg oblika:
| Jezik | Deklaracija funkcije |
Морате бити улоговани како бисте послали задатак на евалуацију.